package 双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author Weton Li
 * @Date 2021/2/27 19:14
 */
public class 二_求三数之和 {


    public static List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums);


        int n = nums.length;

        ArrayList<List<Integer>> list = new ArrayList<>();
        // 从0遍历基准人
        for (int i = 0; i < n; i++) {
            // 判断如果基准人>0，退出循环
            if (nums[i] > 0) break;
            // 判断如果基准人重复出现，仅跳过当次循环
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            // 定义左右指针，定义当前三数和sum
            int lp = i + 1;
            int rp = n - 1;
            // 如果三数和=0，数组转集合，结果追加到事先定义好的List集合中，勿忘左指针右移，右指针左移。
            int sum = nums[lp] + nums[i] + nums[rp];
            while (lp < rp) {
                if (sum == 0) {
                    list.add(Arrays.asList(nums[lp], nums[i], nums[rp]));
                    lp++;
                    rp--;
                    // 移动后左指针或右指针有相同元素，则指针对应继续移动
                    while (lp < rp && nums[lp] == nums[lp - 1]) lp++;
                    while (lp < rp && nums[rp] == nums[rp + 1]) rp--;
                    // 如果三数和<0，左指针右移
                } else if (sum < 0) {
                    lp++;
                    // 如果三数和>0，右指针左移
                } else rp--;
            }
            // 当左指针>右指针||左指针=右指针，有请下一位基准人
        }
        return list;
    }

    public static List<List<Integer>> threeSum1(int[] nums) {


        List<List<Integer>> list = new ArrayList<>();

        int n = nums.length;

        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        list.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    }
                }
            }

        }
        return list;
    }


    public static void main(String[] args) {
        int input[] = {-1, 0, 1, 2, -1, -4};
        System.out.println(threeSum(input));
    }
}
